package algorithm.leetcode.I1201to1400;


import java.util.TreeMap;

public class Q1296 {

    public boolean isPossibleDivide(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>(Integer::compareTo);
        for (int num : nums) map.put(num, map.getOrDefault(num, 0)+1);

        // 循环删除数字
        for (int keyInt : map.keySet()) {
            // 取出map第一个元素keyInt的出现的此处,并将keyInt到keyInt+k-1的次数都减去这个次数,如果中间不够则返回false
            int times = map.get(keyInt);
            if (times > 0) {
                for (int i = 0; i < k; i++) {
                    int newTimes = map.getOrDefault(keyInt + i, 0)-times;
                    if (newTimes >= 0) map.put(keyInt + i, newTimes);
                    else return false;
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Q1296 q1296 = new Q1296();
        System.out.println(q1296.isPossibleDivide(new int[]{1,2,3,7,8,9}, 3));
    }
}
